/*
 * @Author: szx
 * @Date: 2021-10-28 20:26:01
 * @LastEditTime: 2021-10-28 21:00:20
 * @Description:
 * @FilePath: \leetcode\88\88.cpp
 */
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 我直接傻了，用排序方法快
// class Solution {
//    public:
//     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//         for (int i = 0; i != n; ++i) {
//             nums1[m + i] = nums2[i];
//         }
//         sort(nums1.begin(), nums1.end());
//     }
// };

// class Solution {
//    public:
//     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//         vector<int> nums(n + m);
//         int p = 0, p1 = 0, p2 = 0;
//         while (p1 < m && p2 < n) {
//             if (nums1[p1] > nums2[p2]) {
//                 nums[p++] = nums2[p2++];
//             } else {
//                 nums[p++] = nums1[p1++];
//             }
//         }

//         while (p1 < m) {
//             nums[p++] = nums1[p1++];
//         }
//         while (p2 < n) {
//             nums[p++] = nums2[p2++];
//         }

//         for (int i = 0; i < m + n; ++i) {
//             nums1[i] = nums[i];
//         }
//     }
// };
class Solution {
   public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1, p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            nums1[p--] = nums2[p2] > nums1[p1] ? nums2[p2--] : nums1[p1--];
        }
        while (p2 >= 0) {
            nums1[p--] = nums2[p2--];
        }
    }
};
int main() {
    Solution s;
    vector<int> v1 = {1, 2, 3, 0, 0, 0};
    vector<int> v2 = {2, 5, 6};
    s.merge(v1, 3, v2, 3);
    for (auto& i : v1) {
        cout << i << " ";
    }
    return 0;
}